ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group97b.txt/000017_icon-group-sender _Wed Jul 9 11:12:07 1997.msg

Internet Message Format | 2000-09-20 | 1KB

Received: from kingfisher.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Wed, 9 Jul 1997 12:27:03 MST
Received: by kingfisher.CS.Arizona.EDU; (5.65v3.2/1.1.8.2/08Nov94-0446PM)
    id AA25461; Wed, 9 Jul 1997 12:27:03 -0700
Date: Wed, 9 Jul 1997 11:12:07 -0500 (CDT)
Message-Id: <[e-mail]>
X-Sender: [e-mail]
X-Mailer: Windows Eudora Pro Version 2.1.2
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: Icon Group <[e-mail]>
From: Bob Alexander <[e-mail]>
Subject: Re: A small puzzle
Errors-To: [e-mail]
Status: RO

This is a really BORING solution, 'cause it's terribly straightforward, and
probably the same way someone would do it in C, but why not:

  procedure lcp(a,b)
    every i := seq() do
      if not (a[i] == b[i]) then
        return a[1:i]
  end

Or, maybe more efficient but less transparent:

  procedure lcp(a,b)
    every i := seq() do
      if not match(a[i],b,i) then
        return a[1:i]
  end

?

Seems to me that this approach is linear in terms of characters examined
(where n is somehow related to the lengths of the strings involved), as
opposed to several n-squared agorithms I've seen here and in the SNOBOL4 area.

-- Bob